/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***二叉树和数组的转换  数组实现二叉树 前中后序 遍历 ***/
/***C++ 实现版本    written by Daniel           ***/

#include <iostream>
using std::cout;
using std::endl;
//顺序存储二叉树的前序遍历
void preOrder(int *arr, int size, int index)
{
    if (size == 0)
    {
        cout << "数组为空" << endl;
        return;
    }
    cout << arr[index] << "\t";
    if (2 * index + 1 < size)
    {
        preOrder(arr, size, 2 * index + 1);
    }
    if (2 * index + 2 < size)
    {
        preOrder(arr, size, 2 * index + 2);
    }
    return;
}
//顺序存储二叉树的中序遍历
void midOrder(int *arr, int size, int index)
{
    if (size == 0)
    {
        cout << "数组为空" << endl;
        return;
    }
    if (2 * index + 1 < size)
    {
        midOrder(arr, size, 2 * index + 1);
    }
    cout << arr[index] << "\t";
    if (2 * index + 2 < size)
    {
        midOrder(arr, size, 2 * index + 2);
    }
    return;
}
//顺序存储二叉树的后序遍历
void postOrder(int *arr, int size, int index)
{
    if (size == 0)
    {
        cout << "数组为空" << endl;
        return;
    }
    if (2 * index + 1 < size)
    {
        postOrder(arr, size, 2 * index + 1);
    }
    if (2 * index + 2 < size)
    {
        postOrder(arr, size, 2 * index + 2);
    }
    cout << arr[index] << "\t";
    return;
}
int main(int argc, char **argv)
{
    int *arr = new int[8];
    for (int i = 0; i < 8; i++)
    {
        arr[i] = i;
    }
    //调用前序遍历
    preOrder(arr, 8, 0);
    cout << endl;
    midOrder(arr, 8, 0);
    cout << endl;
    postOrder(arr, 8, 0);
    delete arr;
}